//
//  215. 数组中的第K个最大元素.swift
//  Top600
//
//  Created by rjb on 2021/8/4.
//

import Foundation
class Solution215 {
    // 数组中的第K个最大元素
    // 可以采用基于堆的排序算法。采用大顶堆。
    // 采用快速排序。使用从大到小排序。当恰好遇到位置在k-1时为该元素。
    // 两种方法都要掌握
    var result: Int = 0
    func findKthLargest(_ nums:inout [Int], _ k: Int) -> Int {
        var nums = nums
        quickPart(a: &nums, k: k, start: 0, end: nums.count - 1)
        return result
    }
    func quickPart(a: inout [Int], k: Int, start: Int, end: Int) {
        if end < start {
            return
        }
        let mid = part(a: &a, start, end: end)
        if mid == a.count - k {
            result = a[mid]
            return
        }
        quickPart(a: &a, k: k, start: start, end: mid - 1)
        quickPart(a: &a, k: k, start: mid + 1, end: end)
    }
    // 这是一个很巧妙的写法
    func part(a: inout [Int], _ start: Int , end: Int) -> Int{
        let pivot = end
        var counter = start
        for i in start..<end {
            // 如果当前的值小于基准值。就将a[i]的元素放到a[counter]里
            if a[i] < a[pivot] {
               let temp = a[counter]
                a[counter] = a[i]
                a[i] = temp
                counter += 1
            }
        }
        // 最后将a[pivot]的值与a[counter]位置交换
        let tmp = a[pivot]
        a[pivot] = a[counter]
        a[counter] = tmp
        return counter
    }
    static func test() {
        let solution = Solution215()
        var nums = [3,2,1,5,6]
//        var nums = [1]
        let k = 2
        let result = solution.findKthLargest(&nums, k)
        print(result)
    }
}
